Quick Index
Overview


On this page we discuss the ADT (idea) of a dictionary.

These terms used somewhat interchangeably:


Getting Started: Word Dictionary


As an example of a dictionary, let's first look at a common word dictionary.

Common Word Dictionary
WordDefintion
funamusement or enjoyment
algorithma step-by-step procedure for solving a problem
mathematicsthe science of numbers and their operations, ...

Notes:


(we could also say a definition is associated to a word)

Word Dictionary Idea (Generalized)


Let's generalize "Word Dictionary" to "Dictionary". In other words, remove the limitation of handling words only.

Word Dictionary Generalized:

Word DictionaryDictionary
wordkey
definitionvalue
A word associated to a definitionA key associated to a value
word-definition pairkey-value pair

Notes:


The basic idea of a dictionary is that we can lookup a value given a key.

Dictionary (Examples)


Some "Dictionary" examples.

Employee Dictionary (key is employee number, value is Employee object):

KeyValue
1001Employee (Yaping Deng)
1002Employee (Kofi Kinston)
1003Employee (Muhammad Ali)


Color Dictionary (key is color name, value is html HEX value):

KeyValue
BlueViolet#8A2BE2
Black#000000
Blue#0000FF


Course Dictionary (key is course id, value is Course object):

KeyValue
CSCI 1130Course (Introduction to Computer Programming in Java)
CSCI 2001Course (Object Oriented Programming)
CSCI 2002Course (Data Structures and Algorithms)


Dictionary Usage


Examples of fundamental dictionary operations.

Lookup (Get) Example
(pseudocode)
value = get value from dict at key 1002

Expected Result:
Var "value" should be set to Employee object for Kofi Kingston
KeyValue
1001Employee (Yaping Deng)
1002Employee (Kofi Kinston)
1003Employee (Muhammad Ali)
Add (Put) Example
(pseudocode)
In dictionary
at key 1004
set value to Employee object (Jim Thorpe)

Expected Result:
New key-value pair should be added as shown
KeyValue
1001Employee (Yaping Deng)
1002Employee (Kofi Kinston)
1003Employee (Muhammad Ali)
1004Employee (Jim Thorpe)


Association (KeyValue)


We have used the term "association" and "key-value" often in our discussion of Dictionary.

More information on the Association type is here....

Dictionary ADT Spec


The following describes the abstract data type (ADT) for a "Dictionary" type.

Name: Dictionary

Methods:

Method
Name
Method
Parameters
Description
size()Return the number of elements (count)
get(key)Get (and return) the value associated with the parameter "key", or null if not found
put(key, value)Put param "value" at param "key" into this dictionary, replace if already present, otherwise add as new key-value association -- return previous value or null if no previous value
removeKey(key)Remove "key" from dictionary -- return previous value -- if key is not found throw runtime exception -- (see note below)
containsKey(key)Return true if this dictionary contains "key" (otherwise return false)
keys()Return list containing all keys (order of keys is not specified) - return type is a DynamicList
 
getIfAbsentPut(key, providerFct)Get value at "key" -- if "key" is absent, then generate value using param "providerFct" -- return value
removeKeyIfAbsent(key, supplierFct)Remove "key" (association) -- return previous value -- if key is not found then return value from param "supplierFct"
 
bucketCount()Optional method for hashed based classes that use "buckets" -- return the bucket count (i.e., the number of buckets)

Notes on ADT:


Java Dictionary Interface (ADT)


Here is the Java Dictionary Interface (ADT): Start download

Navigation